import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/15 10:12
 * @description 迭代
 */
public class Solution2 {
    public static void main(String[] args) {
        int[] preOrder = {3, 9, 8, 5, 4, 10, 20, 15, 7}, inOrder = {4, 5, 8, 10, 9, 3, 15, 20, 7};
        Solution2 solution2 = new Solution2();
        solution2.buildTree(preOrder, inOrder);
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}
